package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/basic-calculator/description/?envType=study-plan-v2&envId=top-interview-150">基本计算器(Basic Calculator)</a>
 * <p>给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。</p>
 * <p>注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "1 + 1"
 *      输出：2
 *
 * 示例 2：
 *      输入：s = " 2-1 + 2 "
 *      输出：3
 *
 * 示例 3：
 *      输入：s = "(1+(4+5+2)-3)+(6+8)"
 *      输出：23
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= s.length <= 3 * 10^5</li>
 *         <li>s 由数字、'+'、'-'、'('、')'、和 ' ' 组成</li>
 *         <li>s 表示一个有效的表达式</li>
 *         <li>'+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)</li>
 *         <li>'-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)</li>
 *         <li>输入中不存在两个连续的操作符</li>
 *         <li>每个数字和运行的计算将适合于一个有符号的 32位 整数</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/12 11:51
 */
public class LC0224BasicCalculator_H {

    static class Solution {
        public int calculate(String s) {
            Deque<Integer> numberStack = new LinkedList<>();
            Deque<Character> symbolStack = new LinkedList<>();
            // 先把表达式中的空白字符串移除
            s = s.replaceAll(" ", "");
            // 处理'-'作为一元运算的情况：
            // 1.表达式第一个数为负数.例如：-1+2
            // 2.()中第一个数为负数。例如：(-1+2)
            if (s.charAt(0) == '-') {
                s = "0" + s;
            }
            while (s.contains("(-")) {
                s = s.replace("(-", "(0-");
            }
            int currIndex = 0;
            char[] chars = s.toCharArray();
            while (currIndex < s.length()) {
                char ch = chars[currIndex];
                switch (ch) {
                    // 如果是'('
                    case '(':
                        symbolStack.addLast(ch);
                        ++currIndex;
                        break;
                    // 如果是')'：需要在符号栈中寻找'('
                    case ')':
                        while (symbolStack.peekLast() != '(') {
                            calculate(numberStack, symbolStack);
                        }
                        symbolStack.pollLast();
                        ++currIndex;
                        break;
                    // 如果是'+'、'-'
                    case '+':
                    case '-':
                        //// 处理'-'作为一元运算的情况：()中第一个数为负数。例如：(-1+2)
                        //if (currIndex > 0 && (chars[currIndex - 1] == '(' || chars[currIndex - 1] == '+' || chars[currIndex - 1] == '-')) {
                        //    numberStack.addLast(0);
                        //}
                        // 将之前可以进行运算的先运算，再将操作符添加到符号栈
                        while (!symbolStack.isEmpty() && (symbolStack.peekLast() == '+' || symbolStack.peekLast() == '-')) {
                            calculate(numberStack, symbolStack);
                        }
                        symbolStack.addLast(ch);
                        ++currIndex;
                        break;
                    // 如果是数字：向后判断，将连续的数字组成新的数字的添加到数字栈
                    default:
                        StringBuilder stringBuilder = new StringBuilder();
                        stringBuilder.append(ch);
                        ++currIndex;
                        while (currIndex < s.length() && Character.isDigit(chars[currIndex])) {
                            stringBuilder.append(chars[currIndex]);
                            ++currIndex;
                        }
                        numberStack.addLast(Integer.parseInt(stringBuilder.toString()));
                }
            }
            while (!symbolStack.isEmpty()) {
                calculate(numberStack, symbolStack);
            }
            return numberStack.pollLast();
        }

        private void calculate(Deque<Integer> numberStack, Deque<Character> symbolStack) {
            Character symbol = symbolStack.pollLast();
            int num2 = numberStack.pollLast();
            int num1 = numberStack.pollLast();
            if (symbol == '+') {
                numberStack.addLast(num1 + num2);
            } else if (symbol == '-') {
                numberStack.addLast(num1 - num2);
            }
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.calculate("(1+(4+5+2)-3)+(6+8)"));
        System.out.println(solution.calculate("1-(     -2)"));
        System.out.println(solution.calculate("(7)-(0)+(4)"));
    }
}
